package org.example.sword2offer.primary;

/**
 * @author: lynn
 * @Descript: NC133 链表的奇偶重排
 * 给定一个单链表，把所有的奇数节点和偶数节点分别排在一起。
 * 请注意，这里的奇数节点和偶数节点指的是节点编号的奇偶性，而不是节点的值的奇偶性。
 * 请尝试使用原地算法完成。你的算法的空间复杂度应为 O(1)，时间复杂度应为 O(nodes)，nodes 为节点总数。
 * @date: 2021/7/2 9:59
 * @version: 1.0
 */
public class Q79_ReOrderOddEvenListNode {
    public static void main(String[] args) {
        ListNode listNode=new ListNode(1);
        listNode.next=new ListNode(2);
        listNode.next.next=new ListNode(3);
        listNode.next.next.next=new ListNode(4);
        listNode.next.next.next.next=new ListNode(5);
        listNode.next.next.next.next.next=new ListNode(6);
        listNode.next.next.next.next.next.next=new ListNode(7);

        Q79_ReOrderOddEvenListNode q79ReOrderOddEvenListNode =new Q79_ReOrderOddEvenListNode();
        q79ReOrderOddEvenListNode.reOrder(listNode);
        System.out.println("xxxxxx");
    }


    public ListNode reOrder(ListNode node){ //fixme NC133 链表的奇偶重排
        if (node==null || node.next==null ||node.next.next==null) return node;

        ListNode oddNode=node;
        ListNode evenNode=node.next;
        ListNode evenhead=evenNode;
        while (oddNode.next!=null && evenNode.next!=null){ //fixme 条件判断容易出错
          oddNode.next=oddNode.next.next;
          evenNode.next=evenNode.next.next;
          oddNode=oddNode.next;
          evenNode=evenNode.next;
        }
        oddNode.next=evenhead;
        return node;
    }



    public static class ListNode{
        ListNode next;
        int val;
        ListNode(int val){
            this.val =val;
        }
    }
}
